/**
 * 输入一张链表,输出该链表中倒数第 k 个结点
 * 单链表
 * 定义快慢指针,
 */

import java.util.ArrayList;
public class suanfa12 {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }

        public ListNode FindKthToTail(ListNode head, int k) {
            if (k < 0 || head == null) {
                return null;
            }
            ListNode fast = head;
            ListNode slow = head;
            //1 .fast走 k-1步
            while (k - 1 != 0) {
                fast = fast.next;
                if (fast == null) {
                    return null;
                }
                k--;
            }
            //2 , 3
            while (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }

    }
    //快指针走k步,然后慢指针开始走
    public ListNode FindKthToTail2(ListNode head, int k) {
        if(k < 0 || head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(k > 0 && fast != null) {
            fast = fast.next;
            k--;
        }
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return k > 0 ? null : slow;
    }
}
